package com.demo.Sort;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] a = {80, 30, 60, 40, 20, 10, 50, 70};
        shellSort(a, a.length);
        for (int i : a) {
            System.out.print(" "+ i);
        }
    }

    /**
     * @param a 数组
     * @param b 数组长度
     */
    private static void shellSort(int[] a, int b) {
        //c 每次减为原来的一半
        for (int c = b / 2; c > 0; c /= 2) {

        // 共c个组，对每一组都执行直接插入排序
            for (int i = 0; i < c; i++) {

                for (int d = i + c; d < b; d += c) {
                    // 如果a[d] < a[d-c]，则寻找a[d]位置，并将后面数据的位置都后移。
                    if (a[d] < a[d - c]) {
                        int e = a[d];
                        int k = d - c;
                        while (k >= 0 && a[k] > e) {
                            a[k + c] = a[k];
                            k -= c;
                        }
                        a[k + c] = e;
                    }
                }
            }
        }
    }
}
